import sys, os, string, itertools

def iuniq(enu):
    ps, qs = itertools.tee(enu, 2)
    yield next(ps)
    for p, q in itertools.izip(ps, qs):
        if p != q:
            yield p

def read_tokens(prepFilePath):
    tokens = []
    f = open(prepFilePath)
    for line in f:
        line = line.rstrip()
        if line.startswith("#"):
            if line.startswith("# option"):
                if line.find("--getmacrocode") < 0:
                    raise SystemError("c_macro_wordnet requires a preprocessed files with --getmacrocode")
        else:
            fields = line.split("\t")
            if len(fields) == 3:
                tokens.append(fields[2])
    f.close()
    return tokens

class SomeExpression(object):
    def __repr__(self): return "$SOME_EXPRESSION$"
    def __hash__(self): return hash("$SOME_EXPRESSION$")
    def __eq__(self, right): return isinstance(right, SomeExpression)

SOME_EXPRESSION = SomeExpression()

def extract_defines_and_conditions(tokenSeq):
    defines = []; conditions = []
    def extract_defines_i(seq):
        assert seq[0] == "(configure_macro_line"
        assert seq[-1] == ")configure_macro_line"
        if seq[1] == "M_DEFINE":
            name = seq[2]
            if name.startswith("id|"):
                rightWords = []
                for t in seq[3:]:
                    if t == ")configure_macro_line":
                        break # for t
                    elif t.startswith("id|"):
                        rightWords.append(t)
                    else:
                        rightWords = SOME_EXPRESSION
                        break # for t
            if rightWords is SOME_EXPRESSION:
                defines.append(( name, SOME_EXPRESSION ))
            elif len(rightWords) == 0:
                defines.append(( name, None ))
            else:
                defines.append(( name, rightWords ))
        elif seq[1] == "M_IF" or seq[1] == "M_ELIF":
            for t in seq[2:]:
                if t == ")configure_macro_line":
                    break # for t
                elif t.startswith("id|"):
                    conditions.append(t)
    i = 0
    len_tokenSeq = len(tokenSeq)
    while i < len_tokenSeq:
        token = tokenSeq[i]
        if token == "(configure_macro_line":
            startI = i
            i += 1
            endI = None
            while not endI and i < len_tokenSeq:
                token = tokenSeq[i]
                if token == ")configure_macro_line":
                    endI = i + 1
                    break # while not...
                i += 1
            if endI:
                extract_defines_i(tokenSeq[startI:endI])
        else:
            i += 1
    
    return defines, conditions

def remove_prefix(s):
    if s is SOME_EXPRESSION:
        return s
    elif s:
        i = s.find("|")
        if i < 0: return s
        return s[i + 1:]
    

def bild_destination_table(allDefines):
    tbl = dict()
    for src, dst in allDefines:
        tbl.setdefault(src, []).append(dst)
    for src, dsts in tbl.iteritems():
        dsts[:] = list(iuniq(sorted(dsts)))
    return tbl

def find_desitinations(src, tbl):
    curVisited = set()
    foundDsts = []
    def fd_i(n):
        if n in curVisited:
            return
        curVisited.add(n)
        ds = tbl.get(n, None)
        if not ds:
            foundDsts.append(n)
        else:
            for d in ds:
                if isinstance(d, list):
                    foundDsts.append(d)
                else:
                    fd_i(d)
    fd_i(src)
    foundDsts = list(iuniq(sorted(foundDsts)))
    return foundDsts

class __CycleFound(Exception): pass

def find_cycles(tbl):
    cycles = []
    for src in tbl.keys():
        curVisited = set()
        stack = []
        def fc_i(n):
            if stack and n == stack[0]:
                cycles.append(stack)
                raise __CycleFound
            stack.append(n)
            if n in curVisited:
                return
            curVisited.add(n)
            ds = tbl.get(n, None)
            if ds:
                if not isinstance(d, list):
                    for d in ds:
                        fc_i(d)
            stack.pop()
        try:
            fc_i(src)
            assert not stack # empty
        except __CycleFound: pass 
    cycles = filter(lambda c: c[0] == min(c), cycles)
    return cycles

if __name__ == '__main__':
    import getopt
    
    usage = """
usage: c_macro_wordnet.py files...
options
  -d dir: source directory.
  -i filelist: filelist.
  -Dname: additional define.
  -Dname=value: additional define.
  --condition: prints identifiers which used in condtion of #if
  --cycle: prints cycles in definitions.
  --destination: prints all possible destinations.
  --simple: prints a destination for a name when simple value founds.
  --free: prints identifiers which used in condition of #if but not #define'ed.
"""[1:-1]
    
    if len(sys.argv) == 1:
        print usage
        sys.exit(1)
    
    opts, args = getopt.gnu_getopt(sys.argv[1:], "d:i:hD:N:", 
            [ "destination", "simple", "cycle", "free", "condition" ])
    
    MODE_LISTING, MODE_DESTINATION, MODE_SIMPLE, MODE_CYCLE, MODE_FREE, MODE_CONDITION = range(1, 1 + 6)
    
    firstCharOfIdentifierSet = set(string.ascii_letters + "_")
    
    mode = None
    targetFiles = []
    additionalDefs = []
    for k, v in opts:
        if k == "-h":
            print usage
            sys.exit(0)
        elif k == "-d":
            targetDir = v
            for root, dirs, files in os.walk(v):
                files = filter(lambda f: f.endswith(".prep"), files)
                for f in files:
                    targetFiles.append(os.path.join(root, f))
        elif k == "-i":
            for line in open(v):
                fp = line.rstrip()
                targetFiles.append(fp)
        elif k == "-D":
            i = v.find("=")
            if i >= 0:
                name, value = v[:i], v[i+1:]
                assert name[0:1] in firstCharOfIdentifierSet
                if ' ' in value:
                    raise SystemError("complex definition is not supported")
                name = "id|%s" % name
                if not value:
                    additionalDefs.append(( name, None ))
                elif value[0] in string.digits:
                    if set(".eEfFpP").intersection(value):
                        additionalDefs.append(( name, "l_float|%s" % v ))
                    else:
                        additionalDefs.append(( name, "l_int|%s" % v ))
                elif value[0] == '"':
                    additionalDefs.append(( name, "l_string|%s" % v ))
                elif value[0] == "'":
                    additionalDefs.append(( name, "l_int|%s" % v ))
                elif value in ( 'true', 'false' ):
                    additionalDefs.append(( name, "l_bool|%s" % v ))
                else:
                    additionalDefs.append(( name, value ))
            else:
                additionalDefs.append(( v, None ))
        elif k == "-N":
            assert v.find("=") < 0
            additionalDefs.append(( v, None ))
        elif k == "--destination":
            if mode: raise SystemError("two mode options specified")
            mode = MODE_DESTINATION
        elif k == "--simple":
            if mode: raise SystemError("two mode options specified")
            mode = MODE_SIMPLE
        elif k == "--cycle":
            if mode: raise SystemError("two mode options specified")
            mode = MODE_CYCLE
        elif k == "--condition":
            if mode: raise SystemError("two mode options specified")
            mode = MODE_CONDITION
        elif k == "--free":
            if mode: raise SystemError("two mode options specified")
            mode = MODE_FREE
        else:
            assert False
    
    if not mode:
        mode = MODE_LISTING
    
    for a in args:
        targetFiles.append(a)
    
    prepFiles = [(fp + ".prep" if not fp.endswith(".prep") else fp) \
            for fp in targetFiles]
    
    defines = []; conditions = []
    for filePath in prepFiles:
        tokenSeq = read_tokens(filePath)
        ds, cs = extract_defines_and_conditions(tokenSeq)
        defines.extend(ds)
        conditions.extend(cs)
    conditions = sorted(set(conditions))
    
    if mode == MODE_LISTING:
        for name, value in defines:
            if isinstance(value, list):
                print "%s -> %s" % ( remove_prefix(name), " ".join(map(remove_prefix, value)) ) 
            else:
                print "%s -> %s" % ( remove_prefix(name), remove_prefix(value) )
        for d in additionalDefs:
            print "%s -> %s" % tuple(map(remove_prefix, d))
    elif mode == MODE_DESTINATION:
        allDefines = defines + additionalDefs
        tbl = bild_destination_table(allDefines)
        srcs = [src for src, _ in allDefines]
        srcs = sorted(set(srcs))
        for src in srcs:
            dsts = find_desitinations(src, tbl)
            print remove_prefix(src)
            for value in dsts:
                if isinstance(value, list):
                    print "\t%s" % " ".join(map(remove_prefix, value)) 
                else:
                    print "\t%s" % remove_prefix(value)
    elif mode == MODE_SIMPLE:
        allDefines = defines + additionalDefs
        tbl = bild_destination_table(allDefines)
        srcs = [src for src, _ in allDefines]
        srcs = sorted(set(srcs))
        for src in srcs:
            rawSrc = remove_prefix(src)
            dsts = find_desitinations(src, tbl)
            flattenRawDsts = []
            for value in dsts:
                if isinstance(value, list):
                    flattenRawDsts.extend(map(remove_prefix, value))
                else:
                    flattenRawDsts.append(remove_prefix(value))
            flattenRawDsts.sort()
            flattenRawDstSet = set(flattenRawDsts)
            
            simpleTypeTable = { 
                "char":"char", "int8_t":"char", "uint8_t":"char",
                "int":"int", "int16_t":"int", "int32_t":"int", "int64_t":"int",
                "uint16_t":"int", "uint32_t":"int", "uint64_t":"int",
                "bool":"bool",
                "double":"double",
                "float":"float",
                "void":"void"
            }
            simpleValueTable = { "NULL":"NULL" }
            
            if None in flattenRawDstSet:
                print "-N%s" % rawSrc
            else:
                for t, tv in simpleTypeTable.iteritems():
                    if t in flattenRawDstSet:
                        print "-D%s=%s" % ( rawSrc, tv )
                        break # for t
                else:
                    for v, vv in simpleValueTable.iteritems():
                        if v in flattenRawDstSet:
                            print "-D%s=%s" % ( rawSrc, vv )
                            break # for v
                    else:
                        if len(flattenRawDstSet) == 1:
                            frd0 = flattenRawDsts[0]
                            if frd0 is SOME_EXPRESSION:
                                pass
                            elif frd0[0:1] in firstCharOfIdentifierSet:
                                print "-D%s=%s" % ( rawSrc, flattenRawDsts[0] )
    elif mode == MODE_CYCLE:
        firstCharOfIdentifierSet = set(string.ascii_letters + "_")
        allDefines = defines + additionalDefs
        tbl = bild_destination_table(allDefines)
        cycles = find_cycles(tbl)
        for cycle in cycles:
            print " -> ".join(map(remove_prefix, cycle + [ cycle[0] ]))
    elif mode == MODE_FREE:
        allDefines = defines + additionalDefs
        allDefinedNameSet = set(n for n, _ in allDefines)
        
        for c in conditions:
            if c not in allDefinedNameSet:
                print remove_prefix(c)
    elif mode == MODE_CONDITION:
        for c in conditions:
            print remove_prefix(c)
            
